In a forward chaining system, the inference engine begins with facts and moves toward a conclusion, or goal. A forward chaining system works from a list of facts and their corresponding queries. It will examine the rule base after each query to see if any of the rules can be evaluated. It reaches a conclusion when enough facts are answered in a manner to cause one of the rules supplying a conclusion to fire. The order of the queries and, within the queries, the order of the rules affect the order of the search, hence the order of the solutions.
The logic for forward chaining can be expressed as follows:
main:
set pointer to top of rule base
while facts with queries remain
get next fact
if fact not asserted then
prompt user and get answer
assert fact
process_rules(fact)
end if
end while
end main
process rules(fact):
set pointer to top of rule base
while rules remain
get next rule
if rule uses fact then
evaluate rule
if rule evaluates true then
if rule asserts new fact then
assert new fact
process daemons(new fact)
process rules(new fact)
end if
if rule draws conclusion
announce conclusion
end if
end if
end if
end while
end process rules
Note that the call to "process rules" within the routine "process rules" is a recursive call and that it passes in the new fact. Thus, anytime that a fact is asserted when forward chaining, all rules using that fact are evaluated to determine whether a conclusion can be derived. If all of the facts required to evaluate a rule are not asserted, then the inference engine skips the rule.
In our example, the list of facts and their corresponding queries are as shown below. As you will see, the inference engine will examine the facts in the order listed.
fact
passengers
"How many passengers can it carry?",
wheels
"How many wheels does it have?",
"used for cargo"
"Is it used to carry cargo?",
make
"What is the make of the vehicle?"
The next few paragraphs will walk you through the forward chaining inference process using our sample rule base.
You may walk through this example using the shell. Go to the "tutorial shell" card. Click on the "load RB" button to make certain that the rule base is loaded in the "Rule Base" field. Next, if the "Forward Chain/Backward Chain" field does not show "Forward Chain", click on it to toggle it to "Forward Chain".
If you would like to monitor the process, click on the "trace" check box to set trace on (an X will show in the box when it is on). To step through the process, click on the "step" check box to set step on (an X will show in the box when it is on).
Next, click on the "(re)start" button to start the session and answer the questions or follow the directions as they appear in the "Query" field. In this case, you should enter carriage return in the "Answer" field after clicking on "(re)start". During the session you may toggle between this card and others in the stack. The shell will retain its state when you toggle among cards; you do not have to start over each time that you return to the shell.
If you checked both trace and step, watch the "Trace" field to see the actions taken by the system. The system will show the state of the stack in the "Stack" field and the facts and their values in the "Facts" field.
NOTE: The system handles daemons and traces actions with respect to them. You will notice that whenever a fact is asserted, that fact is pushed on the stack while the system looks for daemons associated with it. Therefore, the fact name will appear twice on the stack during that processing. For this tutorial ignore these actions taken by the system concerning daemons.
The system begins with the stack empty, so it looks for the first fact having a query, finds fact "passengers", and pushes it on the stack. It then prompts with the query, which is, "How many passengers can it carry?". Answer "4" in the "Answer" field. The system asserts the fact "passengers = 4" and, after processing daemons, searches the rule base for rules with clauses using fact
"passengers".
The system finds the rule "Corvette", pushes it on the stack, and evaluates it. Rule "Corvette" fails because fact "car" has not yet been asserted, so it is popped from the stack.
The system then resumes the search for rules using fact "passengers" and finds rule "Camaro", pushes it on the stack, and evaluates it. Rule "Camaro" also fails because fact "car" has not been established, so it is popped from the stack.
The system then resumes the search for rules using fact "passengers" and finds rule "car 1", pushes it on the stack, and attempts to evaluate it. Rule "car 1" fails because fact "wheels" has not yet been asserted so rule "car 1" is popped from the stack.
The system continues the search and finds that rule "car 3" uses fact
"passengers", pushes rule "car 3" on the stack, and attempts to evaluate it. Rule "car 3" proves false because the clause does not match fact "passengers" so it is popped from the stack. The clause appears true in the trace but, since there is a NOT preceding the clause, it actually proves false.
No more rules use fact "passengers", so it is popped from the stack.
The stack is now empty, so the system looks for the next fact having a query, finds fact "wheels", and pushes it on the stack. It then prompts with the query, which is, "How many wheels does it have?". Answer "4". The system asserts the fact "wheels = 4" and, after processing daemons, searches for a rule using fact
"wheels".
The system finds rule "car 1", pushes it on the stack, and attempts to evaluate it. The clauses about wheels and passengers prove true, but the rule fails because fact "used for cargo" has not yet been asserted so rule "car 1" is popped from the stack.
The system then resumes the search for rules using fact "wheels" and finds rule
"car 2", pushes it on the stack, and attempts to evaluate it. Rule "car 2" proves false because the clause does not match fact "wheels" so it is popped from the stack. The clause appears true in the trace but, since there is a NOT preceding the clause, it actually proves false.
No more rules use fact "wheels", so it is popped from the stack.
The stack is now empty, so the system looks for the next fact having a query, finds fact "used for cargo", and pushes it on the stack. It then prompts with the query, which is, "Is it used to carry cargo?". Answer "no". The system asserts the fact "'used for cargo' = no" and, after processing daemons, searches for rules using fact "used for cargo".
It finds rule "car 1" and pushes it on the stack. This time it is able to completely evaluate rule "car 1" since facts "wheels", "passengers", and "used for cargo" have all been asserted. Since the clauses match the rules, rule "car 1" fires and the "then" part of the rule is executed, asserting fact "car = true". When fact "car" is asserted, the system pushes it on the stack, processes daemons, and searches for rules using it.
The system first finds "Corvette", pushes it on the stack, and evaluates it. Rule "Corvette" fails because fact "make" has not been established, so it is popped from the stack.
The system resumes the search for rules using fact "car" and finds rule "Camaro", pushes it on the stack, and evaluates it. It also fails to evaluate because fact "make" has not been established, so it is popped from the stack.
The system continues searching for rules using fact "car", finds rule "Mustang", pushes it on the stack, and evaluates it. It too fails to evaluate because fact "make" has not been established, so it is popped from the stack.
Since no other rules use fact "car", it is popped from the stack. Since rule
"car 1" is finished, it too is popped from the stack, leaving "used for cargo" on top of the stack.
The system then resumes the search for rules using fact "used for cargo" and finds rule "car 4", pushes it on the stack, and attempts to evaluate it. Rule
"car 4" fails because the clause doesn't match fact "used for cargo" and it is popped from the stack. The clause appears true in the trace but, since there is a "not" preceding the clause, it actually proves false.
Since no other rules use fact "used for cargo", it is popped from the stack.
The stack is now empty, so the system looks for the next fact with a query, finds fact "make", and pushes it on the stack. It then prompts with the query, which is, "What is the make of the vehicle?". Answer "Chevy". The system asserts fact "make = Chevy" and, after processing daemons, searches for rules using fact "make".
It first finds rule "Corvette", pushes it on the stack, and evaluates it. Rule
"Corvette" evaluates false because fact "passengers" does not match the clause, so it is popped from the stack.
The system resumes the search for rules using fact "make" and finds rule "Camaro", pushes it on the stack, and evaluates it. Rule "Camaro" evaluates true, so the system executes the "then" part of the rule and asserts fact "model = Camaro". It pushes fact "model" on the stack, processes daemons, and searches for rules using it.
It finds no rules using fact "model", so fact "model" is popped from the stack.
The system then executes the next statement in the "then" part of rule "Camaro" and informs the user that "The car is a Camaro."
If you elect to continue, the system pops rule "Camaro" from the stack.
The system then continues searching for rules using fact "make" and finds rule
"Mustang", pushes it on the stack, and evaluates it. Rule "Mustang" proves false because fact "make" doesn't match the clause, so the system pops rule
"Mustang" from the stack.
It then searches for more rules using fact "make" but finds none, so it pops fact "make" from the stack. The system can go no further because there are no more facts having queries.
After walking through the tutorial for the above case, change the order of the fact declarations and watch the response. Change the fact declaration section so that fact "make" precedes fact "passengers" as shown.
fact
make
"What is the make of the vehicle?",
passengers
"How many passengers can it carry?",
wheels
"How many wheels does it have?",
"used for cargo"
"Is it used to carry cargo?"
Now click on "(re)start" and begin the session (do not click on "load RB" or it will restore the rule base to its original condition). During the consultation, you will see that it asks about fact "make" first.
Try the system again, reducing the number of rules. Remember that we had to add rules "car 2", "car 3", and "car 4" to cover the false condition for fact "car". We will now show an alternative to these rules. Click on the "load RB" button to restore the original rule base. Then delete the rules "car 2", "car 3", and
"car 4" in the rule base field and add the "else" clause to rule "car 1" as shown.
rule "car 1"
if
fact wheels = 4 and
fact passengers <= 4 and
fact "used for cargo" = no
then
put true into fact car
else
put false into fact car
Run the system again (don't forget to "(re)start", and observe its actions. You will find that, if you answer facts "wheels", "passengers", or "used for cargo" in a manner that will indicate that the vehicle is not a car, the system will execute the "else" part of the rule and set fact "car" to "false". This achieves the same effect as having rules "car 2", "car 3", and "car 4". You should note that this shortcut can cause problems later if you expand the knowledge in your system with respect to fact "car", unless you remember that you used the shortcut. The purists have reasons for their views!
Feel free to modify the rule base on the "tutorial shell" card and experiment with forward chaining. If you wish to restore the original sample rule base, simply click on the "load RB" button.